\documentclass[10pt,a4paper,titlepage]{article}
\usepackage[latin1]{inputenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage{color}
\usepackage{float}
\usepackage{rotating}
\usepackage{array}

\title{Advanced Algorithms 2012\\Assignment 2: Branch-and-Bound}

\author{Benjamin Johannes Ertl \{gfq406@alumni.ku.dk\}\\Justinas Murzinas \{snp982@alumni.ku.dk\} }

%\institute{Department of Computer Science\\
%University of Copenhagen

%\pagestyle{plain}

\begin{document}

\maketitle

\section*{Question 1}

We can define a 1-tree as a subgraph of a given graph $G$, consisting of two adjacent edges $e_1, e_2$ with minimum cost/distance to an arbitrary node $1$, plus the edges of the minimum spanning tree $T$ on the remaining nodes $\{2,...,n\}$.

Each Hamiltonian tour in $G$ can also be divided into two edges $e_1'$ and $e_2'$ that are incident with node $1$ and a tree $T'$ for the rest of the tour. Therefore, the set of Hamiltonian tours is a subset of 1-trees of $G$.

Since we choose the 1-tree with the two edges $e_1, e_2$ with minimum distance to node $1$ and the minimum spanning tree $T$, it implies that
\[
d_{e_1} + d_{e_2 }\leq d_{e_1'} + d_{e_2'}
\]
\[
d(T) \leq d(T')
\]
for $d_{e_i}$ is the distance of edge $e_i$ and $d(T)$ the sum of all distances in $T$.

Therefore, the cost of our defined 1-tree $T$ is less or equal to the cost of any Hamiltonian tour and a lower bound to the Travelling Salesman Problem.

\section*{Question 2}

A linear program that maximizes the radii of non-overlapping circles can be expressed as following, where $r_i$ is the radius of the circle with center at $i$ and $d(i,j)$ is the distance from center $i$ to center $j$.

\begin{eqnarray*}
\text{MAX    } \sum_{i} r_i \\
\text{S.T.    } r_i + r_j \leq d(i,j),~ \forall i,j, i \neq j \\
r_i \geq 0,~ \forall i
\end{eqnarray*}

\section*{Question 3}

To compute a lower bound for the TSP, we can take the maximum results for the radii of the linear program in Question 2 and multiply them with $2$.

\[
lower bound = \sum_{i} 2 \cdot r_{max_i}
\]

This gives us a lower bound on the TSP, because a salesman must for his tour visit and leave center $i$ at sometime, therefore travel at least $2 \cdot r_{max_i}$ distance for each center $i$, since we computed the maximum radii for each center.
\newpage
\section*{Question 4}

A integer linear program for the TSP can be formulated as following.

\begin{eqnarray*}
\text{MIN    } \sum_{i,j} d_{ij} x_{ij} \\
\text{S.T.    } \sum_{j} x_{ij} = 1,~ \forall i \in V \\
\sum_{i} x_{ij} = 1,~ \forall j \in V \\
u_i - u_j + |V|\cdot x_{ij} \leq |V| -1,~ \forall i, j \in V-\{1\}\\
x_{ij} \in \{0, 1\}~~
u_i \geq 0,~ \forall i, j \in V
\end{eqnarray*}

With
\[
  x_{ij} = \left\{ 
  \begin{array}{l l}
    1 & \quad \text{if edge $(i, j)$ is included}\\
    0 & \quad \text{otherwise}\\
  \end{array} \right.
\]
\[
d_{ij} = \text{distance from vertex $i$ to $j$}
\]

\section*{Question 5}

To get a lower bound for the TSP with the formulated integer linear program in Question 4, we can relax the integrality of the decision variables $x_{ij} \in \{0, 1\}$ to $0 \leq x_{ij} \leq 1$ and take the objective value of the linear program as our lower bound.

\section*{Question 6}

The three lower bound implementations were tested with the three given problems while also changing the configuration. Six different configurations were achieved by uncommenting the given code:
\begin{itemize}
\item sorting the graph edges by length, or leaving it unsorted.
\item by changing the way nodes are selected from the pool (Best-first, Breadth-first, Depth-first).
\end{itemize}

In general sorting never improved performance of any algorithm, compared to the unsorted graph.
Breadth-first, also performed worse. Best-first and Depth-first (with an unsorted graph) showed the best results, while in most cases Best-first was a bit better.

So the best configuration was no-sorting and best-first, while the integer relaxation lower bound produced fewest number of nodes \ref{tbl:t1}. Since the relaxation is formulated as LP which is not very simple to solve, 1-tree was a bit faster for smaller problem instances (even though it evaluated a lot more nodes) \ref{tbl:t2}.

\begin{table}
\begin{center}
\begin{tabular}{|l|c|c|c|}
\hline & Instance1 & Instance2 & Instance3 \\
\hline Path-length & $8.649$ & $19.030$ & $26.753$ \\
\hline nodes generated & $2010$ & $98$ & $77824$ \\
\hline time it took & $48568.26ms$ & $1711.94ms$ & $563877.86ms$ \\
\hline lower bound & relaxation & relaxation & relaxation \\
\hline configuration & No-sorting \& Best-first & No-sorting \& Best-first & No-sorting \& Best-first \\
\hline
\end{tabular}
\end{center}
\caption{The best results for the fewest number of nodes}
\label{tbl:t1}
\end{table}

\begin{table}
\begin{center}
\begin{tabular}{|l|c|c|c|}
\hline & Instance1 & Instance2 \\
\hline Path-length & $8.649$ & $19.030$ \\
\hline nodes generated & $17104$ & $5876$ \\
\hline time it took & $762.46ms$ & $582.23ms$ \\
\hline lower bound & 1-tree & 1-tree \\
\hline configuration & No-sorting \& Best-first & No-sorting \& Best-first \\
\hline
\end{tabular}
\end{center}
\caption{The best time results (Note: for Instance3 it's the same as in the previous table)}
\label{tbl:t2}
\end{table}

\begin{figure}[H]
\begin{center}
\includegraphics
[width=1.0\linewidth]{instance1.png}
\end{center}
\caption{Instance1 TSP solution}
\label{fig:i1}
\end{figure}

\begin{figure}[H]
\begin{center}
\includegraphics
[width=1.0\linewidth]{instance2.png}
\end{center}
\caption{Instance2 TSP solution}
\label{fig:i2}
\end{figure}

\begin{figure}[H]
\begin{center}
\includegraphics
[width=1.0\linewidth]{instance3.png}
\end{center}
\caption{Instance3 TSP solution}
\label{fig:i3}
\end{figure}

\section*{Question 7}

1-tree lower bound performed rather well while solving small TSP instances. This is because finding a 1-tree using a Kruskal's algorithm is a lot faster than solving a linear program. The lower bound is not as accurate though, that is why BnB evaluates a lot more nodes while using it. This becomes very ineffective for large traveling salesman problems. The 1-tree lower bound could be improved by adding weights to the single nodes, so that for example nodes with degree $1$ become more attractive as nodes with degree $> 2$ \cite{3}. This approach would take the assignment condition into account, that is each node in the tour must have degree $= 2$.

Zones lower bound performed the worst. First of all, it is very inaccurate, because the zone of a city is determined mainly from the other nearest cities, so, for example, if we have some clusters of cities that are far from each other, the zones would be small, but the actual distance is not. Due to this inaccuracy BnB has to branch out and evaluate a lot more nodes. This could be improved by adding additional constraints that make use of the fact, that each gap between city clusters must be crossed by any tour at least twice. Theses constraints express the subtour elimination an can be written as formulated in Question 4 or following.
\[
\sum_{i,j\in S} x_{ij} \leq |S| - 1,~ \forall S \subset V, |S| > 1
\]

Integer relaxation lower bound gives the closest result to the actual shortest path. And this makes sense, because the formulation of this LP is almost the same as the formulation of TSP. The lack of integrality doesn't affect the result by much.

\begin{thebibliography}{9}
\bibitem[ITA]{1}
Thomas H. Cormen,
Introduction To Algorithms,
2009.
\bibitem[BnB]{2}
Jens Clausen,
Branch and Bound Algorithms - Principles and Examples
1999
\bibitem[TSP]{3}
Stephan Merens,
TSP Algorithms in Action - Animated Examples of Heuristic Algorithms
http://www-e.uni-magdeburg.de/mertens/TSP/node4.html
\end{thebibliography}

\end{document}
